import functools
class Solution(object):
    def minHeightShelves(self, books, shelfWidth):
        n = len(books)
        @functools.cache
        def dfs(i):
            if i == n:
                return 0
            else:
                now = 0
                height = 0
                min_val = float('inf')
                for k in range(i, n):
                    now += books[k][0]
                    if now <= shelfWidth:
                        height = max(height, books[k][1])
                        min_val = min(min_val, height + dfs(k + 1))
                    else:
                        break
                return min_val

        return dfs(0)
